
function TreeNode(data, left, right) {
    this.data = (data === undefined ? 0 : data)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

function createTree() {
    const a = new TreeNode('a');
    const b = new TreeNode('b');
    const c = new TreeNode('c');
    const d = new TreeNode('d');
    const e = new TreeNode('e');
    const f = new TreeNode('f');
    const g = new TreeNode('g');
    a.left = b;
    a.right = c;
    c.left = d;
    c.right = g;
    d.left = e;
    d.right = f;
    return a;
}

// 前序遍历（非递归版）
function pre(root){
    if(root == null){
        return;
    }

    var res = "";
    var stack = [];
    // 根节点入栈
    stack.push(root);
    while(stack.length != 0){
        // 出栈 并打印
        root = stack.pop();
        res += (root.data + " ");

        // 将右孩子入栈
        if(root.right != null) {
            stack.push(root.right);
        }
        // 将左孩子入栈
        if(root.left != null) {
            stack.push(root.left);
        }
    }
    return res;
}

// 中序遍历（非递归版）
function mid(root) {
    var res = "";
    var stack = [];
    while(true){
        // 当前节点不为空时
        // 入栈, 并指向左孩子
        if(root != null){
            stack.push(root);
            root = root.left;
        }
            // 已经探测到最下边的左孩子
        // 如果栈不为空
        else if(stack.length != 0){
            // 出栈并打印
            root = stack.pop();
            res += (root.data + " ");
            // 访问右孩子
            root = root.right;
        }
        // 栈为空, 遍历完成, 退出
        else{
            break;
        }
    }
    return res;
}

// 后序遍历（非递归版）
function back(root) {
    if(root == null){
        return;
    }

    var preNode = null;
    var res = "";
    var stack = [];
    // 根节点入栈
    stack.push(root);
    while(stack.length != 0){
        // 看一眼栈顶
        root = stack[stack.length-1];
        // 如果没有左右孩子
        if(root.left == null && root.right == null){
            // 出栈 并打印
            root = stack.pop();
            res += (root.data + " ");
            // 记下出栈的节点
            preNode = root;
        }
        // 如果有孩子, 但是孩子已经出栈了
        else if((preNode != null) && (preNode == root.left || preNode == root.right)){
            // 出栈 并打印
            root = stack.pop();
            res += (root.data + " ");
            // 记下出栈的节点
            preNode = root;
        }
        // 将孩子入栈
        else {
            // 将右孩子入栈
            if (root.right != null) {
                stack.push(root.right);
            }
            // 将左孩子入栈
            if (root.left != null) {
                stack.push(root.left);
            }
        }
    }
    return res;
}

// 层次遍历
function line(root) {
    if(root == null){
        return;
    }

    var res = "";
    var queue = [];
    // 根节点 进队列
    queue.push(root);
    while(queue.length != 0){
        // 根节点 出队列
        root = queue.shift();
        res += (root.data + " ");

        // 左右孩子依次进队列
        if(root.left != null){
            queue.push(root.left);
        }
        if(root.right != null){
            queue.push(root.right);
        }
    }
    return res;
}

export default () => {
    var root = createTree();
    return (
        <div>
            <div>前序遍历: {pre(root)}</div>
            <div>中序遍历: {mid(root)}</div>
            <div>后序遍历: {back(root)}</div>
            <div>层次遍历: {line(root)}</div>
        </div>
    );
};